class Solution
{
public:
    // 预处理字符串，根据数据范围，只需处理s的所有长度为1到31的子字符串，复杂度O(km+n)，k大约500，能过
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>> &queries)
    {
        unordered_map<int, vector<int>> numPos;
        vector<vector<int>> result;
        int zeroPos = s.find("0");
        numPos[0] = {zeroPos, zeroPos};
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '0')
            {
                continue;
            }
            for (int j = 1; i + j <= s.size() && j < 32; ++j)
            {
                string numStr = s.substr(i, j);
                int num = stoi(numStr, nullptr, 2);
                if (!numPos.count(num))
                {
                    numPos[num] = {i, i + j - 1};
                }
            }
        }

        for (auto &query : queries)
        {
            int target = query[0] ^ query[1];
            if (numPos.count(target))
            {
                result.push_back(numPos[target]);
            }
            else
            {
                result.push_back({-1, -1});
            }
        }
        return result;
    }

    // 暴力查找，O(mn), 超时
    vector<vector<int>> substringXorQueries2(string s, vector<vector<int>> &queries)
    {
        vector<vector<int>> result;
        unordered_map<int, vector<int>> cache;
        for (auto &query : queries)
        {
            int targetNum = query[0] ^ query[1];

            if (cache.count(targetNum))
            {
                result.push_back(cache[targetNum]);
            }
            else
            {
                string target = binary(targetNum);
                int pos = s.find(target);
                if (pos == string::npos)
                {
                    result.push_back({-1, -1});
                    cache[targetNum] = {-1, -1};
                }
                else
                {
                    result.push_back({pos, static_cast<int>(pos + target.size() - 1)});
                    cache[targetNum] = {pos,
                                        static_cast<int>(pos + target.size() - 1)};
                }
            }
        }
        return result;
    }

    string binary(int x)
    {
        if (x == 0)
        {
            return "0";
        }
        string s;
        while (x)
        {
            if (x & 1)
            {
                s += '1';
            }
            else
            {
                s += '0';
            }
            x /= 2;
        }
        return {s.rbegin(), s.rend()};
    }
};